package com.sukaiyi.leetcode._3longest_substring_without_repeating_characters;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

import static org.junit.jupiter.api.Assertions.*;

/**
 * 无重复字符的最长子串
 * <p>
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 * @author sukaiyi
 * @date 2020/04/17
 * @see <a href="https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/">题目地址</a>
 */
public class Solution {

    @Test
    public void test() {
        assertEquals(lengthOfLongestSubstring("abba"), 2);
        assertEquals(lengthOfLongestSubstring("dvdf"), 3);
        assertEquals(lengthOfLongestSubstring("1111111"), 1);
        assertEquals(lengthOfLongestSubstring("1222222"), 2);
        assertEquals(lengthOfLongestSubstring("abcabcbb"), 3);
    }

    public static int lengthOfLongestSubstring(String s) {
        char[] cs = s.toCharArray();
        int max = 0;
        int i = 0, j = 0;
        Map<Character, Integer> map = new HashMap<>();
        while (j < cs.length) {
            char c = cs[j];
            if (map.containsKey(c) && map.get(c) >= i) {
                max = Math.max(max, j - i);
                i = map.get(c) + 1;
            }
            map.put(c, j++);
        }
        return Math.max(max, j - i);
    }

}
